package cn.fxzhang.leetcode.no10;

 /**
 * 1006. 笨阶乘
 * 按乘法(*)，除法(/)，加法(+)和减法(-)计算阶乘
 * clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1 = 12
 * 类型：递推或找规律
 * 题解：f[i] = i*(i-1)/(i-2)+i-3+f[i-4]-(i-4)*(i-5)/(i-6)*2;
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(2/2)：
 * 执行用时: 0 ms, 击败了100%
 * 内存消耗: 35.3 MB, 击败了54.19%
 *
 * 【中等】通过次数28,332, 提交次数45,267
 * @author 张晓帆
 * @date 2021/4/1
 */
public class P1006_Clumsy_Factorial {

     public int clumsy(int n) {
         int[] init = new int[]{0, 1, 2, 6, 7};
         if (n <= 4){
             return init[n];
         }
         return n%4 == 0? n+1: (n%4 == 3? n-1: n+2);
     }

     /**
      *  执行用时: 10 ms, 击败了14.84%
      *  内存消耗: 37.6 MB, 击败了15.48%
      * @param n
      * @return
      */
    public int clumsy1(int n) {
        int[] init = new int[]{0, 1, 2, 6, 7, 7, 8};
        if (n <= 6){
            return init[n];
        }
        long[] f = new long[n+1];
        f[1] = 1;
        f[2] = 2;
        f[3] = 6;
        f[4] = 7;
        f[5] = 7;
        f[6] = 8;
        for (long i = 7; i <= n; i++){
            int x = (int)i;
            f[x] = i*(i-1)/(i-2)+i-3+f[x-4]-(i-4)*(i-5)/(i-6)*2;
        }
        return (int)f[n];
    }
}
